trait SimpleResults { 
  type Input

  trait Result[+T] {
    def next: Input

    def map[U](f: T => U): Result[U]
    def flatMap[U](f: T => Result[U]): Result[U]
    def flatMapWithNext[U](f: T => Input => Result[U]): Result[U]
    def append[U >: T](alt: => Result[U]): Result[U]
  }

  case class Success[+T](result: T, next: Input) extends Result[T] {
    def map[U](f: T => U)                              = Success(f(result), next)
    def flatMap[U](f: T => Result[U])                  = f(result)   
    def flatMapWithNext[U](f: T => Input => Result[U]) = f(result)(next)    
    def append[U >: T](alt: => Result[U])              = this
  }

  case class Failure(errMsg: String, next: Input) extends Result[Nothing] {
    def map[U](f: Nothing => U)                        = this
    def flatMap[U](f: Nothing => Result[U])            = this
    def flatMapWithNext[U](f: Nothing => Input => Result[U]) = this
    def append[U](alt: => Result[U])                   = alt
  }
}

trait SimpleParsers extends SimpleResults {
  abstract class Parser[+T] extends (Input => Result[T]) { 
    def apply(in: Input): Result[T]

    def flatMap[U](f: T => Parser[U]): Parser[U] 
      = new Parser[U]{def apply(in: Input) = Parser.this(in) flatMapWithNext(f)}

    def map[U](f: T => U): Parser[U] 
      = new Parser[U]{def apply(in: Input) = Parser.this(in) map(f)}
    
    def |[U >: T](p: => Parser[U]): Parser[U] 
      = new Parser[U]{def apply(in: Input) = Parser.this(in) append p(in)}
  
    def ~ [U](p: => Parser[U]): Parser[Pair[T, U]] 
      = for(a <- this; b <- p) yield (a,b)
      // = this.flatMap{a => p.map{b => (a, b)}}
  }  
}

trait StringParsers extends SimpleParsers {
  type Input = String
  private val EOI = 0.toChar
  
  def accept(expected: Char) = new Parser[Char]{
    def apply(in: String) = 
      if(in == "") {
        if(expected == EOI) Success(expected, "")
        else Failure("no more input", in)
      }
      else if(in.charAt(0) == expected) Success(expected, in.substring(1))
      else Failure("expected \'"+expected+"\'", in)
  }

  def eoi = accept(EOI)
}

// a program whose first argument must be "oxo", or "oxo oxo", or "oxo oxo oxo", ...
object OXOParser extends StringParsers {
  def oxo = accept('o') ~ accept('x') ~ accept('o')
  def oxos: Parser[Any] = 
    ( oxo ~ accept(' ') ~ oxos
    | oxo
    )
  
  def main(args: Array[String]) = println((oxos ~ eoi)(args(0)))
}